#include<iostream>
#include<vector>
#include<string>
#include<unordered_set>
#include<unordered_map>
using namespace std; 

//53.最大子数组和
int maxSubArray(vector<int>& nums){
    int n = nums.size();

    //状态表示 dp[i]表示以i位置为结尾，所有子数组中的最大值
    vector<int> dp(n + 1);

    //初始化
    dp[0] = 0;

    //填表
    for (int i = 1; i <= n;i++){
        //状态转移方程
        dp[i] = max(nums[i-1], dp[i - 1] + nums[i-1]);
    }

    //返回值 找到以某个位置为结尾的最大值
    int ret = INT_MIN;
    for (int i = 1; i <= n; i++){
        ret = max(ret, dp[i]);
    }
    return ret;
}


//918.环形子数组的最大和
int maxSubarraySumCircular(vector<int>& nums){
    int n = nums.size();

    //状态表示
    //f[i]表示以i为结尾所有子数组中的最大值；g[i]表示以i为结尾所有子数组中的最小值
    vector<int> f(n + 1);
    vector<int> g(n + 1);

    //初始化
    f[0] = g[0] = 0;

    int fmax = INT_MIN;
    int gmin = INT_MAX;

    //填表
    for (int i = 1; i <= n; i++){
        //状态转移方程
        f[i] = max(nums[i - 1], f[i - 1] + nums[i - 1]);
        g[i] = min(nums[i - 1], g[i - 1] + nums[i - 1]);

        //找到子数组中的最大值和最小值
        fmax = max(fmax, f[i]);
        gmin = min(gmin, g[i]);
    }

    //返回值
    int sum = 0;
    for(auto x : nums){
        sum += x;
    }

    return sum == gmin ? fmax : max(fmax, sum - gmin);
}


//152.乘积最大的子数组
int maxProduct(vector<int>& nums){
    int n = nums.size();

    // 状态表示 f[i]表示以i为结尾时，所有子数组中的最大乘积;g[i]表示以i为结尾时，所有子数组中的最小值
    vector<int> f(n + 1);
    vector<int> g(n + 1);

    //初始化
    f[0] = 1;
    g[0] = 1;

    //填表
    for (int i = 1; i <= n; i++){
        //根据当前位置值的正负分情况讨论状态转移方程
        if(nums[i-1]>=0){
            f[i] = max(nums[i - 1], f[i - 1] * nums[i - 1]);
            g[i] = min(nums[i - 1], g[i - 1] * nums[i - 1]);
        }
        else{
            f[i] = max(nums[i - 1], g[i - 1] * nums[i - 1]);
            g[i] = min(nums[i - 1], f[i - 1] * nums[i - 1]);
        }
    }

    //返回值
    int ret = INT_MIN;
    for (int i = 1; i <= n; i++){
        ret = max(ret, f[i]);
    }
    return ret;
}


//1567.乘积为正数的最长子数组
int getMaxLen(vector<int>& nums){
    int n = nums.size();

    //状态表示
    //f[i]表示以i位置的值为结尾时，乘积为正数的最长子数组长度
    //g[i]表示以i位置的值为结尾时，乘积为负数的最长子数组长度
    vector<int> f(n + 1);
    vector<int> g(n + 1);

    //初始化
    f[0] = 0;
    g[0] = 0;

    //填表
    for (int i = 1; i <= n; i++){
        //根据当前位置值的正负分情况讨论填表,0直接跳过都为0
        if (nums[i - 1] > 0){
            f[i] = f[i - 1] + 1;
            g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
        }
        else if (nums[i - 1] < 0){
            f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            g[i] = f[i - 1] + 1;
        }
    }

    //返回值
    int ret = INT_MIN;
    for (int i = 1; i <= n; i++){
        ret = max(ret, f[i]);
    }
    return ret;
}


//413.等差数列划分
int numberOfArithmeticSlices(vector<int>& nums){
    int n = nums.size();

    //状态表示 dp[i]表示以i位置为结尾所有子数组中有多少个等差数列
    vector<int> dp(n + 1);

    //初始化，等差数列长度必须大于等于3
    dp[0] = 0, dp[1] = 0;

    //填表
    int ret = 0;
    for (int i = 2; i < n; i++){
        //状态转移方程
        if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]){
            dp[i] = dp[i - 1] + 1;
        }
        else{
            dp[i] = 0;
        }

        ret += dp[i];
    }

    //返回值
    return ret;
}


//978.最长湍流子数组
int maxTurbulenceSize(vector<int>& nums){
    int n = nums.size();

    //状态表示
    //f[i]表示以i为结尾的所有子数组中，最后一个状态是上升趋势的湍流子数组的最大长度
    //g[i]表示以i为结尾的所有子数组中，最后一个状态是下降趋势的湍流子数组的最大长度
    vector<int> f(n, 1);
    vector<int> g(n, 1);

    //填表
    int ret = INT_MIN;
    for (int i = 1; i < n; i++){
        //最后一个状态时下降趋势
        if (nums[i - 1] > nums[i]){
            g[i] = f[i - 1] + 1;
        }
        //最后一个状态是上升趋势
        else if (nums[i - 1] < nums[i]){
            f[i] = g[i - 1] + 1;
        }

        ret = max(max(f[i],g[i]), ret);
    }

    //返回值
    return ret;
}


//139.单词拆分
bool wordBreak(string s, vector<string>& wordDict){
    //预处理 先将词典中的字符串存放到哈希表中
    unordered_set<string> hash;
    for(auto str : wordDict){
        hash.insert(str);
    }

    int n = s.size();
    s = " " + s;

    //状态表示 dp[i]表示[0,i]区间的所有拼接字符串是否都存在词典中
    vector<bool> dp(n + 1);

    //初始化
    dp[0] = true;

    //填表
    for (int i = 1; i <= n; i++){
        for (int j = i; j >= 1; j--){
            if(dp[j-1]==true&&hash.count(s.substr(j,i-j+1))){
                dp[i] = true;
                break;
            }
        }
    }

    //返回值
    return dp[n];
}


//467.环绕字符串中的唯一的子字符串
int findSubstringInWraproundString(string s){
    //预处理,建立一个哈希表用来存放以该字符结尾的最大子串个数
    //去重操作，防止字符重复出现，取以该字符结尾的最大的字串个数
    //“对于两个以同一个字符结尾的子串，长的那个子串必然包含短的那个” 这是这道题的关键
    unordered_map<char,int> hash;
    for(auto ch : s){
        hash[ch] = 1;
    }

    int n = s.size();
    //状态表示 dp[i]表示以下标i位置为结尾的字符串有多少子字符串满足条件
    //每个单独的字符都表示一个子串所以初始值设置为1
    vector<int> dp(n,1);

    //填表
    for (int i = 1; i < n; i++){
        if(s[i]-s[i-1]==1||(s[i]=='a'&&s[i-1]=='z')){
            dp[i] = dp[i - 1] + 1;
        }
        //更新哈希表中以该字符结尾的子串最大个数
        hash[s[i]] = max(hash[s[i]], dp[i]);
    }

    //返回值
    int ret = 0;
    for(auto& [ch,count] : hash){
        ret += count;
    }
    return ret;
}


int main(){
    int ret=findSubstringInWraproundString("abaab");

    return 0;
}